package algorithm.swordoff;

import java.util.Deque;
import java.util.LinkedList;
import java.util.Queue;


/**
 * 滑动窗口的最大值
 * 完全参考SQ59_2的思路
 */

public class SQ59_1 {

    public int[] maxSlidingWindow(int[] nums, int k) {
        if (nums.length == 0 || k == 0) return new int[0];

        int[] res = new int[nums.length-k+1];
        MaxWindow maxWindow = new MaxWindow(k);
        for (int i = 0; i < k-1; i++) {
            maxWindow.add(nums[i]);
        }

        for (int i = k-1; i < nums.length; i++) {
            maxWindow.add(nums[i]);
            res[i-k+1] = maxWindow.getMax();
        }

        return res;
    }

    static class MaxWindow {

        private final Queue<Integer> origin;
        // 维护一个不增的双端队列
        private final Deque<Integer> maxVal;
        int windowSize;

        public MaxWindow(int k) {
            origin = new LinkedList<>();
            maxVal = new LinkedList<>();
            windowSize = k;
        }

        public int getMax() {
            if (maxVal.isEmpty()) return -100;
            else return maxVal.peekFirst();
        }

        /**
         * 添加元素的同时保持不增最大队列的不增性
         * @param value
         */
        public void add(int value) {
            origin.add(value);
            while (!maxVal.isEmpty() && maxVal.peekLast() < value) {
                maxVal.pollLast();
            }
            maxVal.addLast(value);

            if (origin.size() > windowSize) pop();
        }

        private void pop() {
            if (!origin.isEmpty() && !maxVal.isEmpty()) {
                int poll = origin.poll();
                if (poll == maxVal.peekFirst()) maxVal.poll();
            }
        }

    }
}
